package com.lql.tree;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 赫夫曼树
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6};
        HuffmanNode huffmanNode = huffmanTree(arr);
        preOrder(huffmanNode);

    }

    /**
     * 根据输入的数组生成对应的赫夫曼树
     *
     * @param arr 数组
     */
    public static HuffmanNode huffmanTree(int[] arr) {

        //遍历arr里的元素放入集合中管理
        ArrayList<HuffmanNode> huffmanNodes = new ArrayList<>();
        for (int value : arr) {
            huffmanNodes.add(new HuffmanNode(value));
        }

        //对集合进行排序
        Collections.sort(huffmanNodes);
        while (huffmanNodes.size() > 1) {
            //取出较小的两个生成节点并删除
            HuffmanNode leftNode = huffmanNodes.remove(0);
            HuffmanNode rightNode = huffmanNodes.remove(0);
            //组成新的节点
            HuffmanNode huffmanNode = new HuffmanNode(leftNode.value + rightNode.value);
            //建立关系
            huffmanNode.leftNode = leftNode;
            huffmanNode.rightNode = rightNode;
            //重新放入集合
            huffmanNodes.add(huffmanNode);
        }
        return huffmanNodes.get(0);
    }

    /**
     * 前序遍历赫夫曼树
     */
    public static void preOrder(HuffmanNode node) {
        if (node == null) {
            System.out.println("树为空");
            return;
        }
        node.preOrder();
    }
}

/**
 * 赫夫曼树的节点
 */
class HuffmanNode implements Comparable<HuffmanNode> {
    public int value;//节点权值
    public HuffmanNode leftNode;//左节点
    public HuffmanNode rightNode;//右节点

    public HuffmanNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(HuffmanNode o) {
        //按照value值从小到大排序
        return this.value - o.value;
    }

    /**
     * 前序遍历赫夫曼树
     */
    public void preOrder() {
        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }
}